The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
In the network, some nodes represent end systems (such as printers, fax machines, telephones, PC's etc) whereas other nodes represent network devices (e.g. switches, routers etc). The data packets are sent around the network from a source to a destination in accordance for example with routing information shared among the nodes of the network. As the network comprises a plurality of interconnected nodes, the network is fairly robust. Should a node or link fail for any reason, the network dynamically configures to re-route data so as to avoid the failed node. When a node or link comes into existence on a network, for instance through repair or by addition of a new node, the network dynamically converges to a so-called converged state wherein all the routers of the network have common routing information.
One class of routing protocol relying on shared information is the link state protocol. Examples of link state protocols are the Intermediate System-to-Intermediate System (IS-IS) protocol and the Open Shortest Path First (OSPF) protocol. A link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link that can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA.
Based on the advertised information in the form of a link state packet (LSP), each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node. A link can be thought of as an interface on a router. The state of the link is a description of that interface and of its relationship to its neighboring routers. A description of the interface may include, for example, the IP address of the interface, the mask, the type of network it is connected to, the router connected to that network and so on. The collection of all link states for the whole network forms the link-state database.
Link state protocols use a link state algorithm to build and calculate the shortest path to all known destinations. The algorithms for determining a shortest path are complicated but the following provides a simplified view of the steps of a link state algorithm. Upon initialization or due to any changing routing information, a router generates a link state advertisement packet (LSP). This advertisement represents the collection of all link states on that router. All routers exchange LSPs by means of flooding. Each router that receives a link state update stores a copy in its link state database and then rapidly propagates the update to other routers. After the database of each router is completed, each router calculates the shortest (lowest cost) path to all designations and uses this information to form an IP routing table. In some instances two or more routers of equal cost present themselves, termed an “equal cost path split.” One appropriate algorithm is a shortest path first (SPF) algorithm.
As a result, a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Conversely, a “reverse spanning tree” can be constructed showing the optimum path to a given node from all nodes from which it is reachable. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning and reverse spanning tree rooted at any other node. The results of the SPF are stored in a routing table (also known as a routing information base (RIB)) and, based on these results, the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately.
In link state protocols, when a link or a node fails and is subsequently repaired, or there is some other change to the network such as a change of link cost, the routers involved with the repaired part of the network then have to re-establish convergence. This is achieved by the router(s) advertising themselves or the change throughout the network area. However, during topology change, there is a short period of time in which LSDBs, RIBs and FIBs across a network become inconsistent as information about a change is propagated through the network. Routes generated during this period of inconsistency may result in routing loops, which persist until the databases have converged, at which point there should be no loops, by definition.
As an example, if a first node sends a packet to a destination node via a second node, comprising the optimum route according to the first node's SPF, a situation can arise where the second node, according to its SPF (based on a different LSDB from that of the first node) determines that the best route to the destination node is via the first node and sends the packet back. The loop can happen where the first node, according to its LSDB believes that a link cost is lower than the second node does, according to its LSDB. This can continue indefinitely although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes. Re-convergence will typically take several hundred milliseconds and hence may cause disruption for periods greater than that originally caused by the failure.
Further, the increase of bandwidth demand in IP networks has led to the deployment of IP over wave division multiplexing (WDM) network infrastructure. In WDM networks, data from different sources may be communicated over the same fiber optic link at the same time, using different wavelengths of light for each data source. Because the Greek letter λ(lambda) is traditionally used to denote wavelength in mathematical expressions, different data sources on a WDM link are sometimes termed “lambdas.” In WDM networks, routers may be interconnected with one or several lambdas provided by the optical layer. Further, dense WDM (DWDM) technology currently allows the multiplexing and de-multiplexing of 16 or more wavelengths within a particular color spectrum, i.e., tens of lambdas.
Since different equipment is typically used to form an IP network and an optical network, common practice in such networks is that different pairs of interconnected routers have a set of lambdas that share a common optical network element. The set of lambdas is termed a Shared Risk Link Group or SRLG to indicate that the failure of the common component can affect multiple resources. For example, a fiber cut would provoke the failure of all lambdas traversing the failed fiber; all the lambdas traversing the fiber would share a common SRLG.
To address convergence problems arising from the use of SRLGs, extensions to the Interior Gateway Protocol (IGP) haven been defined in the context of GMPLS to distribute SRLG. Such extensions are defined in the IETF draft documents entitled “draft-ietf-isis-gmpls-extensions-16.txt” and “draft-ietf-ccamp-ospf-gmpls-extensions-09.txt,” which are currently available at the website of the IETF, at ietf.org. However, existing link state protocols do not make use of this information in their shortest path computation. As a result, a failure of an SRLG may lead to an increase in the time required for router convergence, or may require routers to use non-optimal paths during the period of time in which the SRLG failure is not yet known by every router and those routers have not converged.
Based on the foregoing, there is a clear need for an improved method of determining routing paths that uses information about shared risk link groups.